package 剑指offer_leetcode;

public class 剑指Offer60_n个骰子的点数 {
    //动规
    /**
     *  d[i][j]  -- 当骰子个数为 i ， 点数为 j 时，一共有 多少种组合
     *  dp[i][j] = dp[i-1][j-1] + …… + dp[i-1][i-6]
     *                  1    2   3     4 5  6
     *  dp[1][1] = 1  dp[1][2] = 1 dp[1][3] = 1 …… dp[1][6] = 1
     */
    public double[] dicesProbability(int n) {
        int[][] dp = new int[n+1][6*n +1];
        for(int i=1;i<=6;i++)
            dp[1][i] = 1;

        for(int i=2;i<=n;i++){
            for(int j=i;j<=6 * i;j++){
                for(int k=1;k<=6;k++){
                    if(j<k) break;
                    dp[i][j] += dp[i-1][j-k];
                }
            }
        }

        double[] res = new double[5*n + 1];
        int index = 0;
        double sum = Math.pow(6,n);
        for(int i=n;i<= 6 * n; i++){
            res[index++] = dp[n][i] / sum;
        }
        return  res;
    }

    //暴力
    /**
     *  6 ^ n 种组合
     */
}
